题目大意
给定一个链表以及一个目标值，把小于该目标值的所有节点都移至链表的前端，大于或等于目标值的节点移至链表的尾端，同时要保持这两部分在原先链表中的相对位置。
解题思路
此题并不难，并且可以帮助理解链表。
两个指针，一个负责收集比目标小的，一个收集大于等于目标的。
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| class Solution(object):
def partition(self, head, x):
"""
:type head: ListNode
:type x: int
:rtype: ListNode
"""
dummy = ListNode(-1)
dummy.next = head
small_dummy = ListNode(-1)
large_dummy = ListNode(-1)
# small_prev和large_prev往后遍历增加，small_dummy和large_dummy则负责最后作为返回头结点
small_prev = small_dummy
large_prev = large_dummy
while dummy.next: # head第一个节点
curr = dummy.next
if curr.val < x:
small_prev.next = curr
small_prev = small_prev.next
else:
large_prev.next = curr
large_prev = large_prev.next
dummy = dummy.next
large_prev.next = None # 最后指针置为none
small_prev.next = large_dummy.next # large_dummy对应的是大链表的第一个数
return small_dummy.next # 返回的是small_dummy
|
总结